package com.kabuda.hot100.链表.easy;

import java.util.Stack;

/**
 * @author kabuda
 * @Description
 * @create 2025-02-18 14:09
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 */
public class t206_反转链表 {

    public static void main(String[] args) {
        ListNode headNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        headNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        System.out.println(reverseList2(headNode));
    }


    /**
     * 迭代：双指针
     *
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        ListNode cur = head, pre = null;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 栈：先进后出
     *
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head) {
        if (head == null) return null;

        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;

        // 原节点直接入栈
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        // 新链表头节点取自栈顶
        ListNode newHead = stack.pop();
        ListNode current = newHead;

        // 连接后续节点
        while (!stack.isEmpty()) {
            current.next = stack.pop();
            current = current.next;
        }

        // 切断原链表的正向链接
        current.next = null;

        return newHead;
    }


}


